package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC866 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        public int primePalindrome(int N) {
            if (N <= 2) return 2;
            while (true) {
                int palindrome = nextPalindrome(N);
                if (isPrime(palindrome)) return palindrome;
                N = palindrome + 1;
            }
        }

        // 判断数字是否为质数
        public boolean isPrime(int n) {
            for (int i = 2; i * i <= n; ++i) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }

        // 查找下一个回文数，如果这个数字是递减的，例如654321，那么取这个数的前一半翻转再合并就行，654 456；
        // 但是也有数字如123456，如果翻转合并会得到123321，这个回文数小于N，所以需要判断该数字是否需要改动；
        // 以数字中间那一位为中轴依次向两边看，如果发现左边的数字大于右边，那么数字不需要改动；如果左边数字
        // 大于右边，则需要改动；如果等于，则继续向两边比对
        public boolean needChange(List<Integer> list) {
            int left = list.size() / 2 - 1;
            int right = (list.size() + 1) / 2;
            while (left >= 0 && right < list.size()) {
                if (list.get(left) > list.get(right)) {
                    return false;
                } else if (list.get(left) < list.get(right)) {
                    return true;
                }
                left--;
                right++;
            }
            return false;
        }

        public int nextPalindrome(int n) {
            List<Integer> list = new ArrayList<>();
            // 将数字存入arraylist
            while (n > 0) {
                list.add(0, n % 10);
                n /= 10;
            }

            //如果数字需要改动，那么将左边需要被翻转的数字+1
            if (needChange(list)) {
                int index = (list.size() + 1) / 2 - 1;
                int carry = 1;
                while (index >= 0 && carry > 0) {
                    int val = list.get(index) + carry;
                    carry = val / 10;
                    val = val % 10;
                    list.set(index--, val);
                }
            }
            // 如果第一位是偶数，那么下一个回文数一定以偶数结尾，肯定不是质数（如果N=2会直接返回，不会进入这个函数）,所以第一位数+1
            if (list.get(0) % 2 == 0) {
                list.set(0, list.get(0) + 1);
            }
            int temp = list.size() / 2;
            int result = 0;
            for (int i = 0; i < temp; ++i) {
                result *= 10;
                result += list.get(i);
            }

            // 如果N位数为基数
            if (list.size() % 2 != 0) {
                result *= 10;
                result += list.get(temp);
            }
            for (int i = 0; i < temp; ++i) {
                result *= 10;
                result += list.get(temp - 1 - i);
            }
            return result;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC866 an = new LC866();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
